package leetcode;

/**
 * 动态规划：目标和
 */
public class Solution46 {
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            int sum = 0;
            for(int sums:nums){
                sum = sum + sums;
            }
            //如果target大于sum没有结果
            if(Math.abs(target) > sum){
                return 0;
            }
            if((sum + target) % 2 == 1){
                return 0;
            }
            int bagSize = (sum + target) / 2;
            int[] dp = new int[bagSize + 1];
            dp[0] = 1;
            for(int i = 0;i < nums.length;i++){
                for(int j = bagSize ; j >= nums[i];j--){
                    dp[j] += + dp[j - nums[i]];
                }
            }
            return dp[bagSize];
        }
    }
}
